package 算法.练习1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

/**
 * @author:谢君臣
 * @Date:2021/7/19-19:43
 * @version:1.0
 * @function:
 */
public class LRU {
    public static void main(String[] args) {
        int[][] test = new int[][]{{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}};
        LRU(test, 3);

    }

    public static int[] LRU(int[][] operators, int k) {
        // write code here
        LRUNode lruNode = new LRUNode();
        lruNode.setCapacity(k);
        List<Integer> res = new ArrayList<>();
        for (int[] operator : operators) {
            if (operator[0] == 1) {
                String key = String.valueOf(operator[1]);
                int value = operator[2];
                lruNode.put(key, value);
            } else if (operator[0] == 2) {
                String key = String.valueOf(operator[1]);
                int value = lruNode.get(key);
                res.add(value);
            } else {
                System.out.println("异常输入");
            }
        }
        int[] r = new int[res.size()];
        Iterator<Integer> iterator = res.iterator();
        int i = 0;
        while (iterator.hasNext()) {
            r[i++] = iterator.next();
        }
        return r;
    }

}

class LRUNode {
    class Node {
        private String key;
        private int value;
        private Node next;
        private Node pre;

        public Node() {
        }

        public Node(String key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
            this.pre = null;
        }

        public Node(String key, int value, Node next, Node pre) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.pre = pre;
        }
    }

    public void put(String key, int value) {
        Node node = new Node(key, value);
        this.keyMap.put(key, node);
        if (this.head == null) { // 初始化
            this.head = node;
            this.tail = this.head;
        } else {
            // 先放入
            tail.next = node;
            node.pre = tail;
            tail = node;
            checkSize(); // 再判断
        }
    }

    private void checkSize() {
        if (this.keyMap.size() > this.capacity) {
            this.keyMap.remove(this.head.key);
            this.head.next.pre = null;
            this.head = this.head.next;
        }
    }

    public int get(String key) {
        if (this.keyMap.containsKey(key)) {
            Node node = this.keyMap.get(key);
            int value = node.value;
            if (node == head) {
                put(node.key, node.value);
                this.head.next.pre = null;
                this.head = this.head.next;
            } else if (node == tail) {
                //
            } else {
                node.pre.next = node.next;
                node.next.pre = node.pre;
                node.next = null;
                node.pre = null;
                put(node.key, node.value);
            }
            return value;
        } else return -1;
    }


    private int capacity;
    private HashMap<String, Node> keyMap;
    private Node head; // 头节点
    private Node tail;  // 尾节点

    public LRUNode() {
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
        init(capacity);
    }

    public void init(int capacity) {
        this.capacity = capacity;
        this.head = null;
        this.tail = null;
        this.keyMap = new HashMap<>();
    }
}

